package com.mystudy.leetcode.problem.tree.p_938;


import com.mystudy.leetcode.base.TreeNode;

import java.util.Stack;

/**
 * @program: infoalgorithm
 * @description: 二分搜索树的范围和
 * @author: zhouzhilong
 * @create: 2019-07-23 11:01
 **/
public class Solution {








    /**
     * 土鳖写法，效率低
     * @param root
     * @param L
     * @param R
     * @return
     */
    public int rangeSumBST(TreeNode root, int L, int R) {
        Stack<TreeNode> stack = new Stack<>();
        int sum = 0;
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            if (cur.val >= L && cur.val <= R) {
                sum = sum + cur.val;
            }
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return sum;

    }



    int sum =  0 ;

    /**
     * 前序遍历
     * 递归做法，注意的是递归确实快了一点，但是不知道为啥会快
     * @param root
     * @param L
     * @param R
     * @return
     */
    public int rangeSumBST2(TreeNode root, int L, int R) {
        DFS(root,L,R);
        return sum;
    }
    private void DFS(TreeNode node,int L,int R){
        if(node.val>=L && node.val <= R){
            sum = sum + node.val;
        }
        if(node.right != null){
            DFS(node.right,L,R);
        }
        if(node.left != null){
            DFS(node.left,L,R);
        }

    }


    /**
     * 中序遍历,因为是有顺序的，所以在小于L和大于R的都不用再遍历，
     * 速度最快．
     * @param root
     * @param L
     * @param R
     * @return
     */
    public int rangeSumBST3(TreeNode root, int L, int R) {
        inOrder(root,L,R);
        return sum;
    }
    private void inOrder(TreeNode node,int L,int R){
        if(node == null){
            return;
        }
        if( node.val <L){
            inOrder(node.right,L,R);
        }
        if(node.val>R){
            inOrder(node.left,L,R);
        }

        if(node.val >= L && node.val <=R){
            inOrder(node.left,L,R);
            sum = sum+node.val;
            inOrder(node.right,L,R);
        }
    }





}
